import java.util.Queue;
import java.util.Stack;

public class TreeTest {
    //二叉搜索树与双向链表
    /*
    public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ConvertChild(pRootOfTree);
        while (pRootOfTree.left != null) {
            pRootOfTree = pRootOfTree.left;
        }
        return pRootOfTree;
    }
    public TreeNode prev = null;
    public void ConvertChild(TreeNode root) {
        if (root == null) {
            return;
        }
        ConvertChild(root.left);
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;
        ConvertChild(root.right);
    }
}
     */
    //二叉树创建字符串
    /*
    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        tree2strChilder(root,sb);
        return sb.toString();
    }
    public void tree2strChilder(TreeNode cur,StringBuilder sb) {
        sb.append(cur.val);
        if (cur.left == null && cur.right == null) {
            return;
        }
        if (cur.left != null) {
            sb.append("(");
            tree2strChilder(cur.left,sb);
            sb.append(")");
        } else {
            sb.append("()");
        }
        if (cur.right != null) {
            sb.append("(");
            tree2strChilder(cur.right,sb);
            sb.append(")");
        } else {
            return;
        }
    }
     */
    //中序后序遍历构造二叉树
    /*
    public int i = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = postorder.length-1;
        TreeNode root = buildTreeChilder(inorder,postorder,0,inorder.length-1);

        //prevOrder(root);
        return root;
    }

    public TreeNode buildTreeChilder(int[] inorder,int[] postorder,int begin,int end){
        if (begin > end) {
            return null;
        }
        int n = findIndex(inorder,postorder,begin,end);
        if (n == -1) {
            return null;
        }
        TreeNode root = new TreeNode(inorder[n]);
        TreeNode right = buildTreeChilder(inorder,postorder,n+1,end);
        root.right = right;
        TreeNode left = buildTreeChilder(inorder,postorder,begin,n-1);
        root.left = left;
        return root;
    }
    public int findIndex(int[] inorder,int[] postorder,int begin,int end) {
        while (begin <= end) {
            if (inorder[begin] == postorder[i]) {
                i--;
                return begin;
            }
            begin++;
        }
        return -1;
    }
     */
    //中序与前序遍历构造二叉树
    /*
    public int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        TreeNode root = buildTreeChild(preorder,inorder,0,inorder.length-1);
        return root;

    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int begin,int end) {
        if (begin > end) {
            return null;
        }
        int n = findIndex(preorder,inorder,begin,end);
        if (n == -1) {
            return null;
        }
        TreeNode root = new TreeNode(inorder[n]);
        TreeNode left = buildTreeChild(preorder,inorder,begin,n-1);
        root.left = left;
        TreeNode right = buildTreeChild(preorder,inorder,n+1,end);
        root.right = right;
        return root;
    }
    public int findIndex(int[] preorder,int[] inorder,int begin,int end) {
        while(begin <= end) {
            if (inorder[begin] == preorder[i]) {
                i++;
                return begin;
            }
            begin++;
        }
        return -1;
    }
     */
    //最近公共祖先
    /*
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }
     */

    //最近公共祖先 ---> 非递归做法
    /*public TreeNode prev = null;
    public void getPath(TreeNode cur, TreeNode m, Stack<TreeNode> stack) {
        if (cur == null) {
            return;
        }
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                if (cur == m) {
                    return;
                }
                cur = cur.left;
            } else {
                cur = stack.peek();
                if (cur.right == null || prev == cur.right) {
                    prev = stack.pop();
                    cur = null;
                } else {
                    cur = cur.right;
                }

            }
        }
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
            int size = size1 - size2;
            while (size-- > 0) {
                stack1.pop();
            }
        } else {
            int size = size2 - size1;
            while(size-- > 0) {
                stack2.pop();
            }
        }
        while(!stack1.isEmpty()) {
            if (stack1.peek() == stack2.peek()) {
                return stack1.peek();
            }
            stack1.pop();
            stack2.pop();
        }
        return null;

    }   */
    //求二叉树的叶子节点  --> 子问题思路
    /*
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
     */
    //二叉树的高度
    /*
        int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left + 1 : right + 1;
    }
     */
    //求二叉树第K层节点的个数
    /*
        int getKLevelNodeCount(TreeNode root,int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount((root.right,k-1);
    }
     */
    //二叉树的层序遍历
    /*
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(cur);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list1 = new ArrayList<>();
            while (size-- > 0) {
                TreeNode del = queue.poll();
                list1.add(del.val);
                if (del.left != null) {
                    queue.offer(del.left);
                }
                if (del.right != null) {
                    queue.offer(del.right);
                }
            }
            list.add(list1);
        }
        return list;

    }
     */
    //判断完全二叉树
    /*
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode cur = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(cur);
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            if (top == null) {
                break;
            }
            queue.offer(top.left);
            queue.offer(top.right);
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }
     */
}
